{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Count Nodes That Are Great Enough"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: countGreatEnoughNodes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #计算满足条件的节点数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一棵二叉树的根节点 <code>root</code> 和一个整数 <code>k</code> 。如果一个节点满足以下条件，则称其为 <strong>足够大</strong>&nbsp;：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>它的子树中 <strong>至少</strong> 有 <code>k</code> 个节点。</li>\n",
    "\t<li>它的值 <strong>大于</strong> 其子树中 <strong>至少</strong> <code>k</code> 个节点的值。</li>\n",
    "</ul>\n",
    "\n",
    "<p>返回满足条件的节点数。</p>\n",
    "\n",
    "<p>如果 <code>u == v</code> 或者 <code>v</code> 是 <code>u</code> 的祖先，则节点 <code>u</code> 在节点 <code>v</code> 的 <strong>子树</strong> 中。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>root = [7,6,5,4,3,2,1], k = 2\n",
    "<b>输出：</b>3\n",
    "<b>解释：</b>节点编号从 1 到 7。 \n",
    "节点 1 的子树中的值：{1,2,3,4,5,6,7}。由于节点的值等于 7，有 6 个节点的值小于它的值，因此它是“足够大”的。 \n",
    "节点 2 的子树中的值：{3,4,6}。由于节点的值等于 6，有 2 个节点的值小于它的值，因此它是“足够大”的。 \n",
    "节点 3 的子树中的值：{1,2,5}。由于节点的值等于 5，有 2 个节点的值小于它的值，因此它是“足够大”的。 \n",
    "其他节点不满足条件。 \n",
    "参考下面的图片可以帮助你得到更好的理解。</pre>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2023/07/25/1.png\" style=\"padding: 10px; background: rgb(255, 255, 255); border-radius: 0.5rem; width: 300px; height: 167px;\" /></p>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>root = [1,2,3], k = 1\n",
    "<b>输出：</b>0\n",
    "<strong>解释：</strong>节点编号从 1 到 3。 \n",
    "节点 1 的子树中的值：{1,2,3}。由于节点的值等于 1，没有节点的值小于它的值，因此它不是“足够大”的。 \n",
    "节点 2 的子树中的值：{2}。由于节点的值等于 2，没有节点的值小于它的值，因此它不是“足够大”的。 \n",
    "节点 3 的子树中的值：{3}。由于节点的值等于 3，没有节点的值小于它的值，因此它不是“足够大”的。 \n",
    "参考下面的图片可以帮助你得到更好的理解。\n",
    "</pre>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2023/07/25/2.png\" style=\"padding: 10px; background: rgb(255, 255, 255); border-radius: 0.5rem; width: 123px; height: 101px;\" /></p>\n",
    "\n",
    "<p><strong class=\"example\">示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>root = [3,2,2], k = 2\n",
    "<b>输出：</b>1\n",
    "<strong>解释：</strong>节点编号从 1 到 3。 \n",
    "节点 1 的子树中的值：{2,2,3}。\n",
    "由于节点的值等于 3，有 2 个节点的值小于它的值，因此它是“足够大”的。 \n",
    "节点 2 的子树中的值：{2}。由于节点的值等于 2，没有节点的值小于它的值，因此它不是“足够大”的。 \n",
    "节点 3 的子树中的值：{2}。由于节点的值等于 2，没有节点的值小于它的值，因此它不是“足够大”的。 \n",
    "参考下面的图片可以帮助你得到更好的理解。\n",
    "</pre>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2023/07/25/3.png\" style=\"padding: 10px; background: rgb(255, 255, 255); border-radius: 0.5rem; width: 123px; height: 101px;\" /></p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>树中的节点数在范围&nbsp;<code>[1, 10<sup>4</sup>]</code> 内。<span style=\"display: none;\">&nbsp;</span></li>\n",
    "\t<li><code>1 &lt;= Node.val &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>1 &lt;= k &lt;= 10</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [count-nodes-that-are-great-enough](https://leetcode.cn/problems/count-nodes-that-are-great-enough/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [count-nodes-that-are-great-enough](https://leetcode.cn/problems/count-nodes-that-are-great-enough/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[7,6,5,4,3,2,1]\\n2', '[1,2,3]\\n1', '[3,1,2]\\n2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    # # dfs\n",
    "    def countGreatEnoughNodes(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        self.res = 0\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return []\n",
    "\n",
    "            lis = sorted(dfs(node.left) + dfs(node.right) + [node.val])[:k]\n",
    "            if lis[-1] < node.val:\n",
    "                self.res += 1\n",
    "\n",
    "            return lis\n",
    "\n",
    "\n",
    "        dfs(root)\n",
    "        return self.res     \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    # # dfs\n",
    "    def countGreatEnoughNodes(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        self.res = 0\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return []\n",
    "\n",
    "            lis = sorted(dfs(node.left) + dfs(node.right) + [node.val])[:k]\n",
    "            if lis[-1] < node.val:\n",
    "                self.res += 1\n",
    "\n",
    "            return lis\n",
    "\n",
    "\n",
    "        dfs(root)\n",
    "        return self.res     \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def countGreatEnoughNodes(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        self.res = 0\n",
    "        def dfs(node):\n",
    "            if not node: return []\n",
    "            lis = sorted(dfs(node.left) + dfs(node.right) + [node.val])[:k]\n",
    "            if lis[-1] < node.val: self.res += 1\n",
    "            return lis\n",
    "        dfs(root)\n",
    "        return self.res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGreatEnoughNodes(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        def dfs(u):\n",
    "            nonlocal cnt\n",
    "            if not u: return []\n",
    "            if not (u.left or u.right): return [u.val]\n",
    "            cur = sorted(dfs(u.left) + dfs(u.right) + [u.val])[:k]\n",
    "            if len(cur) == k and u.val > cur[-1]: cnt += 1\n",
    "            return cur\n",
    "        \n",
    "        cnt = 0\n",
    "        dfs(root)\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGreatEnoughNodes(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        self.res = 0\n",
    "        def dfs(node):\n",
    "            if not node: return []\n",
    "            lis = sorted(dfs(node.left) + dfs(node.right) + [node.val])[:k]\n",
    "            if lis[-1] < node.val: self.res += 1\n",
    "            return lis\n",
    "        dfs(root)\n",
    "        return self.res     \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def countGreatEnoughNodes(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        def dfs(u):\n",
    "            nonlocal cnt\n",
    "            if not u: return []\n",
    "            if not (u.left or u.right): return [u.val]\n",
    "            cur = sorted(dfs(u.left) + dfs(u.right) + [u.val])[:k]\n",
    "            if len(cur) == k and u.val > cur[-1]: cnt += 1\n",
    "            return cur\n",
    "        \n",
    "        cnt = 0\n",
    "        dfs(root)\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def countGreatEnoughNodes(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        ans = 0\n",
    "\n",
    "        def f(node):\n",
    "            nonlocal ans \n",
    "            if not node:\n",
    "                return []\n",
    "            l, r = f(node.left), f(node.right)\n",
    "            res = sorted(l + r + [node.val])[:k]\n",
    "            if len(res) == k and node.val > res[-1]:\n",
    "                ans += 1\n",
    "            return res \n",
    "            \n",
    "        f(root)\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def countGreatEnoughNodes(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        self.res = 0\n",
    "        def dfs(node):\n",
    "            if not node: return []\n",
    "            lis = sorted(dfs(node.left) + dfs(node.right))[:k]\n",
    "            if (p := bisect.bisect_left(lis, node.val)) >= k:\n",
    "                self.res += 1\n",
    "                return lis[:k]\n",
    "            else: return lis[:p] + [node.val] + lis[p:k-1]\n",
    "        dfs(root)\n",
    "        return self.res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def countGreatEnoughNodes(self, root: Optional[TreeNode], k: int) -> int:\n",
    "        self.res = 0\n",
    "        def dfs(node):\n",
    "            if not node: return []\n",
    "            lis = dfs(node.left) + dfs(node.right)\n",
    "            lis.sort()\n",
    "            p = bisect.bisect_left(lis, node.val)\n",
    "            if p >= k:\n",
    "                self.res += 1\n",
    "                return lis[:k]\n",
    "            else: return lis[:p] + [node.val] + lis[p:k-1]\n",
    "        dfs(root)\n",
    "        return self.res\n",
    "        \n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
